package leetCode;

public class MaximizeDistancetoClosestPerson {
	public int maxDistToClosest(int[] seats) {
		int n = seats.length;
		int[] right = new int[n];
		for (int i = 0; i < right.length; i++) {
			right[i] = n;
		}
		int first1 = 0;// 第一个出现1的位置
		boolean no1 = true;
		int last = -1;// 上一个为1的位置
		for (int i = 0; i < n; i++) {
			if (seats[i] == 1) {// 左边的right设置为i
				if (no1) {
					no1 = false;
					first1 = i;
				}
				if (last != -1) {
					right[last] = i;
				}
				last = i;
			}
		}
		int res = 1;
		for (int i = 0; i < right.length; i++) {
			if (seats[i] == 1) {
				if (right[i] != n) {
					res = Math.max(res, (right[i] - i) / 2);
				} else {
					res = Math.max(res, n - 1 - i);
				}
			}
		}
		res = Math.max(res, first1);
		return res;
	}

	public static void main(String[] args) {
		int[] seat = { 0, 0, 1, 0, 0, 0, 0 };
		System.out.println(new MaximizeDistancetoClosestPerson().maxDistToClosest(seat));
	}
}
